struct ListNode
{
    int val;
    ListNode *next;ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        if(list1 == nullptr || list2 == nullptr)
        {
            return list1 == nullptr ? list2 : list1;
        }

        ListNode* newnode = list1->val > list2->val ? list2 : list1;
        if(newnode == list1)
        {
            newnode->next = mergeTwoLists(newnode->next, list2);
        }
        else
        {
            newnode->next = mergeTwoLists(newnode->next, list1);
        }
        return newnode;
    }
};